//稀疏矩阵
// Created by liweimin on 2021/7/7.
//

#ifndef DATA_STRUCTURE_SPARSE_MATRIX_H
#define DATA_STRUCTURE_SPARSE_MATRIX_H

#endif //DATA_STRUCTURE_SPARSE_MATRIX_H

#define MAX_SIZE 12500 //最多元素
#define MAX_RC 100  //最大行数
#define ElemType int

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef struct
{
    int i, j;//矩阵下标
    int e;//值
} Triple;

typedef struct
{
    Triple data[MAX_SIZE + 1];//非零元三元组表 0号位置未使用
    int mu, nu, tu;//矩阵行数、列数、非零元个数
} Matrix;

typedef struct
{
    Triple data[MAX_SIZE + 1];
    int rpos[MAX_RC + 1];//各行第一个非零元的位置表
    int mu, nu, tu;//矩阵行数、列数、非零元个数
} SMatrix;

//---------稀疏矩阵的十字链表存储表示-----------
typedef struct OLNode
{
    int i, j;//非零元下标
    ElemType e;//值
    struct OLNode *right, *down;//左边和下边的元素
} OLNode, *OLink;

typedef struct
{
    OLink *rhead, *chead;//把头
    int mu, nu, tu;//行数、列数、非零元个数
} CrossList;

bool createCrossList(CrossList *crossList)
{
    if (crossList)crossList = NULL;
    int m, n, t;
    scanf("%d %d %d", &m, &n, &t);
    getchar();
    crossList->mu = m;
    crossList->nu = n;
    crossList->tu = t;
    if (!(crossList->rhead = (OLink *) malloc(m + 1) * sizeof(OLink)))return false;
    if (!(crossList->chead = (OLink *) malloc(m + 1) * sizeof(OLink)))return false;
    for (int i = 1; i <= m; ++i)
    {
        crossList->rhead[i] = NULL;//初始化右把头
    }
    for (int j = 1; j <= n; ++j)
    {
        crossList->chead[j] = NULL;//初始化下把头
    }
    int i, j, e;
    for (scanf("%d %d %d", &i, &j, &e); i != 0; scanf("%d %d %d", &i, &j, &e))
    {
        OLNode *p, *a;
        if (!(p = (OLNode *) malloc(sizeof(OLNode)))) return false;
        p->i = i;
        p->j = j;
        p->e = e;
        if (crossList->rhead[i] == NULL || crossList->rhead[i]->j > p->j)//第一个节点或者把头
        {
            p->right = crossList->rhead[i];
            crossList->rhead[i] = p;
        } else
        {
            for (a = crossList->rhead[i]; a->right && a->right->j < j; a = a->right);//行插
            p->right = a.right;
            a.right = p;
        }

        if (crossList->chead[j] == NULL || crossList->chead[j]->i > p->i)//第一个节点或者把头
        {
            p->down = crossList->chead[j];
            crossList->chead[j] = p;
        } else
        {
            for (a = crossList->chead[j]; a->down && a->down->i < i; a = a->down);//列插
            p->down = a.down;
            a->down = p;
        }
    }
    return true;
}

void transposeMatrix(Matrix M, Matrix *T)
{
    T->mu = M.mu;
    T->nu = M.nu;
    T->tu = M.tu;
    int q = 1;
    for (int col = 1; col < = M.nu; ++col)//列数
    {
        for (int i = 1; i <= M.tu; ++i)//元素个数
        {
            if (M.data[i].j == col)
            {
                T->data[q].e = M.data[i].e;
                T->data[q].j = M.data[i].i;
                T->data[q].i = M.data[i].j;
                q++;
            }
        }
    }
}

/**
 * 快速转置
 * @param M
 * @param T
 */
void fastTransposeMatrix(Matrix M, Matrix *T)
{
    T->mu = M.mu;
    T->nu = M.nu;
    T->tu = M.tu;
    if (!M.tu)return;
    int num[M.nu + 1] = {0};//每列非零元的个数，初始化为0
    int cpot[M.nu + 1] = {0};//每列第一个非零元在数组中的存储位置
    cpot[1] = 1;//第一列 第一个
    for (int col = 1; col <= M.tu; ++col)
        num[M.data[col].j]++;//得出每列非零元个数

    for (int i = 2; i <= M.tu; ++i)
        cpot[i] = cpot[i] + num[i - 1];//获取每列第一个非零元素的在T中的存储位置

    for (int j = 1; j < = M.tu; ++j)
    {
        int a = M.data[j].j;
        int b = cpot[a];
        T->data[b].j = M.data[j].i;
        T->data[b].i = M.data[j].j;
        T->data[b].e = M.data[j].e;
        ++cpot[a];
    }
}

void multMatrix(SMatrix m, SMatrix n, SMatrix *q)
{
    if (m.nu != n.mu)return;
    //矩阵q初始化
    q->mu = m.mu;
    q->nu = n.nu;
    q->tu = 0;
    if (m.tu * n.tu != 0)//非零矩阵
    {
        int ccol;
        for (int i = 1; i <= m.mu; ++i)
        {
            int ctemp[MAX_SIZE + 1] = {0};

            q->rpos[i] = q->tu + 1;//每行第一个非零元在数组中存储的位置
            int tp;//数组中下一个非零元位置
            if (i < m.mu)
            {
                tp = m.rpos[i + 1];
            } else tp = m.tu + 1;

            for (int a = m.rpos[i]; a < yp; a++)//遍历非零元
            {
                int brow = m.data[a].j;//获取非零元的列数

                int t;

                if (brow < n.mu)t = n.data[brow + 1];
                else
                    t = n.tu + 1;
                for (int b = n.rpos[brow]; b < t; ++b)
                {
                    ccol = n.data[b].j;
                    ctmp[ccol] += m.data[a].e * n.data[b].e;
                }
            }
            for (ccol = 0; ccol < q->mu; ccol++)
            {
                if (ctemp[ccol])
                {
                    q->tu++;
                    if (q->tu > MAX_SIZE)return;
                    q->data[q->tu].e = ctemp[ccol];
                    q->data[q->tu].i = i;
                    q->data[q->tu].j = ccol;
                }

            }
        }
    }
}